package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author Amos
 * @date 2022/6/11
 */

public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {-9, 78, 0, 23, -567, 70};
//        System.out.println(Arrays.toString(arr));

        // 创建要给80000个随机的数组
        int[] arr = new int[80000000];
        for (int i = 0; i < 80000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000)数
        }

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间是=" + date1Str);

        quickSort(arr, 0, arr.length - 1);
        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间是=" + date2Str);
//        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int base = arr[left];
        int i = left;
        int j = right;
        while (i != j) {
            // 先由j从右往左检索比基准数小的
            // 如果检索到比基准数大的或者相等的，就继续检索
            while (arr[j] >= base && i < j) {
                j--; // j从右往左移动;
            }
            // i从左往有检索
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 代码走到这里i停下了，j也停下了，然后交换i和j位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 如果上面while循环的条件不成立，会跳出这个循环，往下执行
        // 如果这个条件不成立，说明i和j相遇了
        // 如果i和j相遇了，就交换基准数这个元素和相遇位置的元素
        // 把相遇位置的元素赋值给基准数这个位置的元素
        arr[left] = arr[i];
        // 把基准数赋值给相遇位置的元素
        arr[i] = base;
        // 基准数在这里就归为了，左边的数字都比他小，右边的都比他大
        // 排基准数的左边
        quickSort(arr, left, i - 1);
        // 排右边
        quickSort(arr, j + 1, right);
    }
}
